1. Field of the Invention
This invention relates to security passwords and more particularly to a method and system for generating secure pronounceable passwords.
2. Description of the Related Art
Poorly chosen passwords continue to be a major cause of security breaches. The increasing popularity of such products as the Unix Operating System and the Kerberos Authentication Protocol in commercial environments accentuate this problem, as both are vulnerable to security breaches by dictionary attacks which search for poor passwords.
Given the choice, most users choose passwords from a "likely password" key space, K.sub.1, that is a small fraction of the entire key space, K, available to them. This smaller key space is typically composed of bad passwords and bad noisy passwords. Bad passwords are those chosen from natural language, jargon, acronyms, dates, or other numeric series, and/or derivatives thereof. Bad noisy passwords consist of a bad password plus noise (e.g. tiger2 or compquter). The small size of K.sub.1, facilitates breaches of security through exhaustive searches of the "likely password" key space, which can be performed using conventional techniques and technologies that are well known in the art. For instance, in the Unix operating system (see Morris, R. and K. Thompson. "Password security: A case history", Communications of the ACM, 22(11), November 1979), user passwords are transformed using a one way function based upon the data encryption standard (DES) (see Data Encryption Standard, National Bureau of Standards, Federal Information Processing Standards, Publication No. 46-1 (Jan. 15, 1977)), and then stored in a password file that is usually accessible to a number of individuals and is in all cases accessible to the administrators of the system to which the password provides access. As the one way function itself is not secret, an adversary can methodically apply this function to all words in K.sub.1, and then compare the results to those in the password file. The Kerberos Authentication Protocol (see Kohl, J. C. Neuman and J. Steiner, "The Kerberos Network Authentication Service", MIT Project Athena (Oct. 8, 1990) Version 5, Draft 3), is also vulnerable to such dictionary attacks as, for reasons not relevant here, the protocol makes it possible for an adversary having a user password to request server access to encrypted messages. Further, by eavesdropping on the network, the adversary can also obtain additional encrypted messages which can be decrypted using the same exhaustive key search technique on K.sub.1.
The size of the key space that can be searched efficiently by an adversary is much larger than is usually believed by most users. Karn and Feldmeier have discussed the size of the key space that can be searched using conventional techniques and technology. (See Karn, P. R. and D. C. Feldmeier, "UNIX password security--Ten years later", Advances in Cryptology--CRYPTO '89, G. Brassard (Ed.) Lecture Notes in Computer Science, Springer Verlag, 1990). Although this discussion is directed towards UNIX password security, the Karn and Feldmeier analysis is widely applicable to typical systems which have artificially small password key space and are therefore susceptible to a key search attack. Protection against such attacks can be enhanced by either altering the system itself, for instance, as proposed by Bellovin and Merritt to secure Kerberos (see Bellovin, S. and M. Merritt, "Encrypted Key Exchange" IEEE Computer Society Symposium on Security and Privacy, May 1992, Oakland, Calif.) or enlarging the size of the likely password key space K.sub.1 until it approaches the size of K, where K is very large. Another approach to improving password security is to establish a system to select a random password of key space K for the user. This later approach, however, can be particularly unfriendly to the user and can lead to users maintaining a written ledger of their passwords to avoid having to memorize a long and arbitrarily selected password.
As noted above, attackers typically attack passwords using dictionary attacks. Either (i) by eavesdropping on the network or (ii) by requesting from a security server, e.g. in the Kerberos (KOHL90) system, or from a file on a system, the attacker can obtain several strings each of which represents known plaintext encrypted with user passwords, e.g. in UNIX a string of zeroes is encrypted with the user password. The attacker then attempts to decrypt these strings by methodically trying passwords from a dictionary of commonly used passwords, and obtain the original plaintext. A related approach which uses less time (but more space) is to pre-compute the encryption of all the passwords in the dictionary, so once the strings are obtained, a simple look up is all that is needed to obtain the user password.
There are at least three approaches to solving the problem of poorly chosen user passwords, and each has its field of use. First, smart cards or token authenticators can be used to completely replace the password. Second, proactive password checkers which examine passwords and do not allow bad passwords to be utilized can be used. Finally, a password generator can be used by the system to generate secure passwords for the users.
Recently, an improved technique for proactive password checking has been described in U.S. patent application Ser. No. 08/121,852, filed Sep. 17, 1993, entitled Method and System for Proactive Password Validation, (Attorney Docket No. 680-072), which is also assigned to the assignee of all rights in the present application. As described the technique provides a proactive password validation method and system which will protect against the selection of bad passwords belonging to a dictionary of bad passwords as well as bad noisy passwords. The on-line generation of bad noisy passwords is not required. The technique does not require the storage of a dictionary of bad passwords or large amounts of data, and can easily be installed in a distributed computing environment. Utilizing the technique, password validation can be performed quickly. After defining the bad password characteristics off-line, the actual validation of the proposed password can be performed on-line, in real time, using minimal amounts of computing power.
With respect to password generators, there are two types of such generators which are known in the art. One type generates completely random passwords which are, by definition, guaranteed to be "good". This type of generator has, however, the significant disadvantage of making the password unpronounceable, and thus hard to remember, and more likely to be written down, which has a security cost, or forgotten, which has an administrative cost.
The second type generates a random, yet pronounceable password for the user, on the assumption that a pronounceable password is easier to memorize, and consequently less likely to be written down or forgotten, and hence, more user friendly and secure. This type of generator typically works by combining random character generation with the rules for pronunciation to generate strings which are pronounceable. There are at least two important aspects to such a generator. First, the passwords must be pronounceable. Since the so called "rules" of pronunciation are fairly inexact, this is a somewhat subjective issue. Secondly, the generated password must be secure. Several pronounceable password generators have been designed, perhaps the two most prominent being that developed by Morrie Gasser [GASS77] in 1977, which is being adopted as a standard by NIST [FIPS92], and that developed by IBM and used by Sandia Labs.
Turning now to attacks on system security, the object of an attacker is either to break into any account(s) on the system or break into a particular account on the system. The former is the more typical vulnerability which most systems face. While it can be argued that the motives of an attacker will differ for each situation, any password system must evaluate security in terms of the difficulty of an attacker targeting any, rather than one particular, account. This is because it is the more common attacker motive and, further, because a system secure against this attacker objective is automatically secure against an attack on a single specific account, although the converse is not true. Consequently parameterizing a system on the basis of the total number of users within the "security domain" being protected is of primary importance.
It will be helpful here to define several parameters:
K, as discussed above, is the absolute size of the password space.
K.sub.1 is the actual space the attacker needs to search in order to break into a particular user's account.
N is the number of users in the "security domain". The definition of "security domain" is situation specific. Some concrete examples would be: a DEC VMS multiuser minicomputer; a network of SUN workstations and servers which use a common/etc/passwd file managed by the NIS name server, or a Kerberos realm serving an entire organization. The number of users within these domains could range from 50 users on a minicomputer to several thousand users being served by a common Kerberos server.
T is the assumed maximum time in seconds which the attacker can spend on the attack. T depends on many factors including the time interval, t, between which password aging is enforced i.e. the period after which a user is required to change passwords. When an attacker captures strings encrypted with passwords, a limited time is available to complete the dictionary attack before the passwords change. For instance, after time t/2, it is likely that half the passwords captured by the attacker have changed, and by time t, all the passwords have changed. Depending on the system other factors may also come into play.
E is the encryptions per second for the particular password scheme, which the most powerful attacker is likely to perform. This parameter, to a great extent, will be determined by the type of computing platform which the attacker has access to. Since this "access" could be illegal this is a difficult number to calculate. Unless the attacker in question is a large organization, like the espionage branch of a foreign government, it may be practical to assume that the attacker has access to a high end personal computer or workstation or a UNIX or other high power server. The parameter E can be calculated in various ways, see for instance Karn and Feldmeir's (KARN89) analysis.
C is an implementation specific constant which corresponds to the effort which must be expended by the attacker on a per user basis for a specific system. For instance, in a UNIX system the attacker searching through a dictionary of a given size would, because of salting (see Morris, R. and K. Thompson "Password security: A case history", Communications of the ACM, 22 (11), November 1979), have to actually be searched through a number of dictionary words equal to the dictionary size multiplied by a factor of 4096. Thus in this particular case, the implementation constant C would be 4096. However, the implementation constant C could be reduced if the attacker uses pre-encrypted dictionaries and has sufficient space on his computing platform to store the salted variations and if the time to search is small as compared to the time required to encrypt. As can be seen from the above example, the constant C can be properly chosen only when specific details of the attack are known.
Based on these parameters, the criterion for protection against a dictionary attack can be defined. The first criterion, which at times is the only one considered by the designers of systems is:
Criterion 1: K&gt;ExTxC
According to this criterion, a password space must be chosen which is large enough so as not to be easily broken by an attacker in a "reasonable" time. Gasser's analysis adds two closely related, very useful criterion, namely:
Criterion 2: The probability of occurrence of the most probable passwords in the password space should be low.
So for instance, although the maximum password space K is very large, the fact that users choose common natural language words with a very high probability can, by itself, make the system vulnerable to dictionary attacks. Gasser discusses the criterion in the context of pronounceable password generators, wherein he points out that it is of no benefit to have an overall maximum key space K which is very huge if a few passwords have a very high probability of being generated, and are generated very frequently by the system thus resulting in the actual key space K.sub.1 being too small. A closely related criterion, which appears to be implicit in Gasser's discussion of the password probability distribution is:
Criterion 3: All passwords in the password space must be of roughly equally probable.
This is really a generalization of Criterion 2, and ensures that there does not exist a subset of the maximum password space K which is so small that it can be easily attacked in lieu of the entire space K to breach system security.
Criterion 4: In an N user system with an actual password space of size K.sub.1, the attacker should have to search, on average, a password space of ##EQU1## in order to break into any one account. This can be expressed as: ##EQU2## Since the attacker need only, on average, search through half any given space to expect to find a password, the more precise figure is K.sub.1 /2N. Criterion 4 may be used in place of Criterion 1 since any system meeting Criterion 4 will, by definition, meet Criterion 1, whereas the converse is not true.
Criterion 5: It should not be possible to divide the password space into B buckets or categories, b.sub.1, b.sub.2, . . . , b.sub.B, from which users choose passwords, with the probability of users choosing passwords from a respective bucket being p.sub.1, p.sub.2, . . . , p.sub.B, such that p.sub.i &gt;.vertline.b.sub.i .vertline./K.sub.1 where b.sub.i is the smallest bucket.
Meeting Criterion 5 is a necessary, but not a sufficient, condition for meeting Criterion 4. It ensures that the smallest bucket or category is large enough to thwart the attacker. The security of the system, in terms of password space size, is as secure as the size of the smallest bucket.
The "Sandia System" is a pronounceable password generator distributed by Sandia Labs along with a version of the Kerberos V source code, see files 7clcpwd.c and 7cldpwd.c in Sandia's Kerberos V distribution. The Sandia System works as follows:
25 templates have been created to represent typical rules of pronunciation in English, for instance "cvcvcvc" is a template representing words formed by a vowel followed by a consonant followed by a vowel. . .
The templates are formed from sets representing, vowels, consonants, double vowels, ending vowels, etc.
To generate a password the system randomly indexes into one of the 25 templates i.e. buckets, all 25 templates being equally likely to be picked.
The system then picks, at random, a password from that particular template, this being a 7 character password.
In order to inflate the password space, either 1 of 10 digits, or 1 of 26 alphabet letters, is randomly added to the password, to bring the total password size to 8 characters. If the eighth character is a digit from 0 to 9, then because there are 10 choices of digits and the digit can be added in any one of eight positions, the password space is expanded by a factor of 80. If one of the characters from A to Z is randomly added to the string, then the effective password space is increased 208 fold.
Users are presented with several such passwords and asked to pick one.
The addition of the eighth character may make the password fairly difficult to pronounce, especially when the eighth character/digit appears in the middle of a pronounceable syllable. Further, presenting users with several choices and letting them pick one, introduces another filter through which selected passwords must pass. It is conceivable that the passwords picked by users are actually from a much smaller space than would be suggested by the system parameters. However, no evaluation has been performed to determine if this is indeed the case. Since the 25 template-buckets are indexed into with uniform probability, it is likely that 1/25th or 4% of all users in a N user system pick passwords from a particular template or bucket. Given the number of characters in the set of vowels, consonants, etc., the size of each template or bucket can be calculated. The size of each of the templates, without the addition of the random eighth character is shown in FIG. 1.
As shown in FIG. 1, the distribution is highly non-uniform, with most of the passwords in a few large buckets. This dramatically affects the security of the system. The total space K of 7 character passwords is 71,213,792, and after inserting the eighth character the total space K expands to an impressive 14.5 billion. However, in a 100 user system, 4 uses picked passwords from the smallest bucket, which has a mere 135,800 7 character passwords, and the eighth character increases the password space to only 27 million. While an attacker may balk at searching through 14.5 billion passwords, a space of 27 million can be searched without excessive effort in order to break into 4 user accounts on a hundred user system. Still further, the attacker would on average have to search through less than 3.5 million passwords to break into 1 account on a 100 user system.
The Gasser/NIST system, which as noted above, is being adopted by NIST, see FIPS92, works as follows:
There are 34 units, the characters A to Z, except Q, and the characters CH, GH, PH, RH, SH, TH, WH, QU and CK; each unit having an associated probability of selection which corresponds roughly to the probability of the occurrence in English of the applicable unit's character.
A series of rules determine which units may appear where in a generated password. These rules are encoded in two tables, i.e. the unit and diagram tables. The former describes special rules for determining where the units may appear, and whether they are vowels or consonants, etc. The latter describes the rules for determining if two units can be juxtaposed.
To generate a password the system selects the first unit, from one of the 34 units, based on the probability of occurrence associated with each of the units.
The system then forms syllables by selecting successive units from the 34 units, based on the rules in the unit and diagram tables. These syllables are then concatenated together to form the password.
If a particular selected unit is inappropriate in a particular position within the password, that unit is rejected, and another unit is selected. If the substitute unit is also rejected, another unit is picked. This process is repeated 100 times, after which the entire syllable is rejected. As noted by Gasser, see GASS77, the limit of 100 is rarely reached.
The Gasser/NIST system has been analyzed in GASS77 and FIPS92. The total password space K is of size 18 million for 6 character passwords, 5.7 billion for 8 character passwords and 1.6 trillion passwords for 10 character passwords. The most probable passwords have a low probability of occurrence. The probability of occurrence of most passwords are roughly equal.
Though not part of the NIST standard, Gasser describes a slight modification to the system which guarantees that all passwords are equally likely. Pursuant to this modification, the system generates the passwords completely at random.
In the Gasser/NIST system each unit represents a bucket of passwords. However, unlike the Sandia System which randomly indexes into the buckets, in the Gasser/NIST system the probability that a user selects a password from a particular bucket is determined by the probabilities associated with the individual units. In the Gasser variation mentioned above, the probability of selecting from a particular bucket, is not the probability associated with the unit, but rather the probability given by the ratio of the size of the bucket to the total size of the password space.
The distribution of passwords into buckets in the Gasser/NIST system is shown below in FIG. 2A. FIG. 2A represents the distribution of passwords generated by a Gasser/NIST system completely at random. As the passwords are generated randomly, sorting the sample into buckets will reflect the actual distribution of passwords into buckets.
As can be seen, the distribution of passwords is highly non-uniform. However, unlike the Sandia system, all the buckets themselves are not equi-probable. That is, the probability of any given password appearing in a given bucket, is dependent on the size of the bucket and is different from the probability of a bucket itself; the latter being the probability that the system chooses that bucket to generate a password. Rather, the probability that a bucket is chosen by the system is tied to the probabilities assigned to the individual units. FIG. 2B juxtaposes the distribution of the passwords into buckets with the probability of a particular bucket being chosen. For purposes of FIG. 2B, it is assumed that there is an equal probability that a user will pick a password from any of the particular buckets.
As can be seen from FIG. 2A there are several very small buckets, i.e. the buckets for R, T, X, GH, SH, TH, QU and CK. FIG. 2B suggests that rather than attacking the smallest bucket itself, it is more beneficial for the attacker to attack the small buckets with a relatively high probability of being chosen, e.g. the buckets for R and T. It is likely that slightly less than 5% of users will have passwords generated from the R bucket and another 5% from the T bucket. Yet the size of the R bucket is a mere 0.31% of the overall password space K, and the T bucket a mere 0.22%. Consequently, an attacker could break into 4 accounts of a 100 account system after searching through only 12.5 million passwords, and might break into one account, on average, after searching 1.6 million passwords. Using the Gasser variant, i.e. where passwords are generated randomly, the probability of a user having a password generated from a bucket is exactly equal to the size of the bucket. So for instance, instead of 5% of users having passwords from the R or T bucket, only approximately 0.3% of users have passwords generated from this bucket. The number of accounts that can be compromised, on average, is thereby decreased, but the problem remains that a rather limited search by an attacker will result in a breach in the system security.
Another pronounceable password generator has been developed by Digital Equipment Corporation and will be referred to as the DEC system. The DEC system utilizes a Markov model to train samples of natural language. Markov models are discussed in more detail below in describing the preferred embodiment of the present invention. Suffice it to say at this point that this training yields a transition probability matrix.
The DEC system generator then utilizes the transition probability matrix developed using the Markov model to probabilistically determine the next state. For example, from the state "Q" it is highly likely that the next state is a "U" if the english language is being utilized. After selecting a certain number of characters, the system requires that the information content of the portion of the password formed at this point be calculated. This is done using a well-known mathematical formulation for information content. Additional characters are then added until the information content meets a predetermined threshold value. The threshold value is selected so as to ensure that the pronounceable password generated is not a bad password, i.e. one selected from natural language, jargon, acronyms, dates, or other derivative thereof.
However, the DEC system likewise suffers from the smallest bucket attacks which have been discussed above with regard to the Sandia system and Gasser/NIST systems. This appears to be caused by the transition probabilities utilized by the system. In particular, the DEC system, as understood, uses buckets which are created based upon the transition probabilities of characters, i.e. unigrams, bigrams, etc., occurring in the English language. Because these transition probabilities vary, the Markov model develops buckets of passwords which are small and buckets of passwords which are large. Stated another way, characters with a greater transition probability in the English language will be generated more often than those with a lower probability in the English language. Thus, the number of users using generated passwords with characters having a high transitional probability in the English language is increased.
It is therefore an object of the present invention to provide an improved method and system for generating pronounceable passwords which provides greater security than conventional systems and techniques. It is a further object of the present invention to provide a method and system for generating pronounceable passwords which requires that an attacker perform a more exhaustive search to uncover one or more of the passwords being utilized by the system users. It is yet another object of the present invention to provide a method and system for generating pronounceable passwords which provides increased security for a user account. It is a still further object of this invention to provide a method and system for generating pronounceable passwords which are not subject to a smallest bucket attack. It is still another object of this invention to provide a method and system which can be utilized to quickly generate secure, pronounceable passwords. It is yet a further objective of this invention to provide a method and system for generating secure, pronounceable passwords which are user friendly.
Additional objects, advantages and novel features of the invention will become apparent to those skilled in the art upon examination of the following as well as by practice of the invention. While the invention is described below with reference to preferred embodiments for generating pronounceable passwords, it should be understood that the invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional applications, modifications and embodiments in other fields (including, but not limited to, those relating to smart cards, automatic tellers and automatic locks), which are within the scope of the present invention as disclosed and claimed herein and in which the present invention could be of significant utility.